#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using i128 = __int128;
const int N = 1e6 + 5;

int a[N];

void minx(int n, int k) {
    deque<int> q1;
    for (int i = 0; i < n; i++) {
        while (!q1.empty() && a[i] < a[q1.back()]) q1.pop_back();
        if (!q1.empty() && q1.front() < i - k + 1) q1.pop_front();
        q1.push_back(i);
        if (i >= k - 1) cout << a[q1.front()] << " ";
    }
    return;
}
void maxx(int n, int k) {
    deque<int> q2;
    for (int i = 0; i < n; i++) {
        while (!q2.empty() && a[i] > a[q2.back()]) q2.pop_back();
        if (!q2.empty() && q2.front() < i - k + 1) q2.pop_front();
        q2.push_back(i);
        if (i >= k - 1) cout << a[q2.front()] << " ";
    }
    return;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i];
    minx(n, k);
    cout << endl;
    maxx(n, k);
    cout << endl;

    return 0;
}